package _6subset;

import java.util.*;

/**
 * @author Gong Cheng
 * @date 2021/1/15 10:02 上午
 **/
public class subsets90 {

    /**
     * 在上一题的第一个解增加了两部
     * 先对输入的数组的排序
     * 对结果去重
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i <nums.length ; i++) {
            int resSize = res.size();
            for (int j = 0; j <resSize ; j++) {
                List<Integer> arrays = new ArrayList<>(res.get(j));
                arrays.add(nums[i]);
                if(!res.contains(arrays)){
                    res.add(arrays);}
            }
        }
        return res;
    }

    /**
     * 回溯法，相同的数跳过
     */

    public List<List<Integer>> subsetsWithDup2(int[] nums){
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        getAns(nums, 0 ,new ArrayList<>(),ans);
        return ans;
    }

    private void getAns(int[] nums,int start, ArrayList<Integer> temp, List<List<Integer>>ans){
        ans.add(new ArrayList<>(temp));
        for (int i = start; i < nums.length ; i++) {
            // 和上个数字相等就跳过
            if(i > start && nums[i] == nums[i - 1]){
                continue;
            }
            temp.add(nums[i]);
            getAns(nums, i + 1,temp, ans);
            temp.remove(temp.size() - 1);
        }
    }
}
